package gold.contest;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC5229 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int maximumsSplicedArray(int[] nums1, int[] nums2) {
            int n = nums1.length, sum1 = 0, sum2 = 0;
            int[] gain1 = new int[n], gain2 = new int[n];

            for (int i = 0; i < n; i++) {
                sum1 += nums1[i];
                sum2 += nums2[i];
                gain1[i] = nums2[i] - nums1[i];
                gain2[i] = nums1[i] - nums2[i];
            }

            int ans1 = sum1 + maxSequence(gain1);
            int ans2 = sum2 + maxSequence(gain2);
            return Math.max(ans1, ans2);
        }

        int maxSequence(int arr[]) {
            int len = arr.length, maxsum, maxhere;
            maxsum = maxhere = arr[0];   //初始化最大和为arr[0]
            for (int i = 1; i < len; i++) {
                if (maxhere <= 0)
                    maxhere = arr[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为arr[i]
                else
                    maxhere += arr[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
                if (maxhere > maxsum) {
                    maxsum = maxhere;  //更新最大连续子序列和
                }
            }
            return maxsum;
        }
    }

    public void run() {
        System.out.println(new Solution().maximumsSplicedArray(InputUtil.toIntegerArray("[60,60,60]"), InputUtil.toIntegerArray("[10,90,10]")));
        System.out.println(new Solution().maximumsSplicedArray(InputUtil.toIntegerArray("[20,40,20,70,30]"), InputUtil.toIntegerArray("[50,20,50,40,20]")));
        System.out.println(new Solution().maximumsSplicedArray(InputUtil.toIntegerArray("[7,11,13]"), InputUtil.toIntegerArray("[1,1,1]")));

    }

    public static void main(String[] args) throws Exception {
        LC5229 an = new LC5229();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
